package com.company.Mergesort;

public class mergesort {

    public static void main(String[] args) {

        int[] arrs = {1,234,34,2,123,11,34,11};

        fz(arrs,0,arrs.length-1);

        for (int arr : arrs) {

            System.out.println(arr);

        }
    }

    //合并：m是中点
    public static void merge(int[] nums,int l , int m , int r)
    {
        int L_size = m-l;
        int R_size = r-m+1;
        int[] left = new int[L_size];
        int[] right = new int[R_size];


        int i, j;
        for(i=l; i<m; i++){	//	将左边放到一块 ，踩坑---细节 i = l,因为后面递归会重复调用merge函数，所以 i 初始值并不是等于 0，应该等于 l
            left[i - l] = nums[i];
        }
        for(j=m; j<=r; j++){	// 将右边放到一块
            right[j-m] = nums[j];
        }
        i = 0; j = 0; int k = l;

        while(i<L_size && j<R_size){	//左右比较大小，将小的元素放进结果nums ,有一方达到顶端就停止
            if(left[i] < right[j]){
                nums[k] = left[i];
                k++;
                i++;
            }else{
                nums[k] = right[j];
                k++;
                j++;
            }
        }
        while(i < L_size){		// 若左边或右边还有元素剩余，则把剩余元素 依次添加到结果nums后面
            nums[k] = left[i];
            k++;
            i++;
        }
        while(j < R_size){
            nums[k] = right[j];
            k++;
            j++;
        }



    }

    //分治
    public static void fz(int[] arrs , int l ,int r)
    {
        int m = (l+r)/2;

        if (l==r)
        {
            return;
        }
        else
        {
            fz(arrs,l,m);
            fz(arrs,m+1,r);
            merge(arrs,l,m+1,r);

        }

    }

}
